import * as THREE from "../../../modules/three/three.module.js";
import {MouseButton, r2d} from "../lib/CommonConsts.js";
import {findConvexHull, flatten, toFixedVector} from "../lib/util/StaticMethods.js";
import {mergeVertices, mergeBufferGeometries} from "../../../modules/three/jsm/utils/BufferGeometryUtils.js";
import {arrAsubB, removeArrayItem} from "../lib/util/ToolMethods.js";
import {PlaneHelper2} from "./PlaneHelper2.js";
import {updateDebugTriangle} from "../scene/EditOrientation.js";
import ConvexAreaMesh from "../lib/gadget/ConvexAreaMesh.js";
import CutPointsDivider, {createParams} from "./CutPointsDivider.js";
import UndoSlice from "./UndoSlice.js";
import SurfaceRoutePlan, {ConfigRoute} from "./SurfaceRoutePlan.js";

/**
 * 已知 模型上的两个点 和相机的位置，三个顶点可以创建一个切割平面A，和一个切割三角形abc
 * 找出b3dms模型中的所有 和 切割三角形abc 有交集 tile网格（tile网格 这里看作是六面几何体），这些与平面A有交集的tile 记为 S 集合。
 *
 * 每个tile 其实是若干个三角形面片拼接出来的，对于集合S 的每个tile，筛选出所有的 和切割三角形abc有交集三角面片，两个三角面片有交集时，会出现一个线段，这个线段同时处于两个三角面片内，所有的交集线段放入一个数组 Arr 中，所有交集三角面片放入 数组ArrTriangles中
 * 数组 Arr 中的所有线段进行排序，使得每个线段首尾相连，组成一条连续折线，折线的第一段是数组的第一个元素，最后一段是数组的最后一个元素
 *
 * 这条折线，其实就是切割三角形abc，在整个模型中刻出的，完全贴合在整个模型上。
 * 需要至少三条这种折线，可以组成一个闭合区域，需要计算出组成这个闭合区域的所有三角面片。这些三角面片 要么是三个顶点全部来自模型（记为1类），要么是有一个或两个顶点或0个顶点来自模型 其余顶点来自切割折线（记为2类）。如何找出闭合区域所有三角面片？
 *
 * 2类三角面片来自于所有和折线有交集三角面片，设一个三角面片和若干个折线有交集；可以把三角面片和若干个折线投影到一个辅助平面，把三维点 投影成二维坐标；
 * 然后使用一种二维图形布尔运算库（比如 BoolPolygonsUtil 运算库），计算出三角形和多边形的并集 图形，对这个并集 图形使用三角剖分，得到的若干三角面片都是属于 2类。
 *
 * 如何找出所有1类三角面片？利用面片之间的邻接关系，先找一个和折线有交集三角面片，遍历该三角面片的所有邻接面片，找出一个位于折线轮廓内的邻接面片，以该邻接面片为起始，以数组ArrTriangles中的三角面为搜索边界， 进行广度优先搜索，所有能够搜索到三角面片都属于1类三角面片。
 * 对于一种特殊的很少出现的情况，存在一个网格孤岛位于折线闭合区域内；则这个网格孤岛的所有三角面片可能应该被归类为1类三角面片，但是不能被搜索到；这种网格孤岛情况应该极难出现，可以先不考虑；即使以后需要处理这种，可以新增交互和算法来从网格孤岛中拾取三角面片。比如点选网格孤岛中的任意一个三角面片，通过广度优先搜索，该孤岛的所有三角面片都能找出来
 *
 * 另一种找出所有1类三角面片的办法：不利用面片之间的邻接关系，所有完全位于切割体积内三角面片（不包含任何ArrTriangles中的元素）记为集合N，多数情况下，可以认为集合N 就是需要找出的所有1类三角面片；也可能出现集合N中的三角面片需要进一步剔除，才是期望的结果；如果通过观察发现 集合N中有需要剔除的三角面片；这时就需要 用户对集合N进行手动点选，剔除不需要的网格孤岛。
 *
 * 最终把所有找到的1类三角面片和 2类三角面片进行合并，得到一个网格，包含了所有顶点的三维坐标和三角索引数组indices，一起传递给后端，为AI航线计算提供所有需要的基础数据
 *
 * meshToTriangles 返回的结果，可以缓存，保存tile瓦片网格和三角面片集合的对应关系；
 * 如何找出所有的2类三角面片？
 * 对切割形成的若干个折线进行精简，把所有折线按照邻接关系，划分为若干个图，一个图中不但包含所有线段，也包含所有线段的顶点；如果一个图中顶点不包含鼠标射线的撞击点坐标，则这个图应该被剔除；这样剔除下来，通常情况下，只剩一个图。剩下的图会有一个闭合的切割轮廓，所有穿过切割轮廓的三角面片，记为集合S。
 * 一个三角面片对应多个折线，即一个三角面片能被多个折线切割。一个折线只能切割一个三角面片。三角面片 和 折线的对应关系是 1 : n (n >= 1)
 * 对集合S中的每个三角面片，计算出这个三角面片被哪些折线切割。一个三角面片通常被多个折线切割为两个或多个部分，如果判断哪个部分是切割区域内的？
 * 做这个判断前，需要给每条折线都绑定切割平面，就是说可以通过折线来找到它属于哪个切割平面；若干个部分中，如果有顶点位于某个切割平面下，则这个部分应该剔除；剔除完毕后，剩下的部分就是切割区域内的。
 * 如何对切割区域内的部分进行三角剖分？
 * 首先对三角面片对应的多条折线，进行首尾相连的排序，得到点数组 array。
 * 最麻烦的情况是有两个三角面片的顶点位于切割平面上方。假设点A ，点B属于三角面片。
 * 创建两条向量A -> B 和 array[0] -> array[last]; 如果两个向量同向（点乘为正数），则轮廓序列为 [...array, B, A] 否则为 [...array, A, B] ;
 * 其他情况是有一个 或 零个三角面片的顶点位于切割平面上方，这时假设点A ，属于三角面片并且位于多个切割平面上方，则
 * 轮廓为[...array, B, A]，如果点A 不存在，轮廓序列直接就是 array。
 * 对轮廓进行三角剖分，得到的新的三角面片都是属于二类。
 *
 * 如何找出所有的1类三角面片？先只支持凸包切割。
 * 所有切割平面为围成一个三维锥体，三维锥体的底面无限向远处延伸，变大。所有位于切割平面上方的三角面片，记为集合P。
 * 集合P的某个子集，就是位于切割区域内的。只考虑邻接关系，不一定能找出所有的1类三角。
 * 如果一个三角面片，既属于集合P，又和2类三角面片 的原始三角面片邻接，则必然位于切割区域内。有些孤岛三角面片，不满足第二个条件，但也应该算作切割区域内，
 * 这时就需要用户进一步点选，来补充出哪些三角面片，无人机喷涂时不可忽略这些三角。
 *
 * 也可以 任选一个2类三角面片 的原始三角面片，求这个三角面片的所有邻居，从这些邻居中选一个在切割平面上方的，以这个邻居作为广度优先搜索的起始点。
 */

const _triangle = new THREE.Triangle();
// const _cutPlane = new THREE.Plane();
const _planeStart = new THREE.Plane();
const _planeEnd = new THREE.Plane();
const _v0 = new THREE.Vector3();
const _v1 = new THREE.Vector3();
const _v2 = new THREE.Vector3();
const _v3 = new THREE.Vector3();
const _normal = new THREE.Vector3();
const _line = new THREE.Line3();
const _line1 = new THREE.Line3();
const _box = new THREE.Box3();
const cameraUp = new THREE.Vector3(0, 1, 0);
const cameraLeft = new THREE.Vector3(-1, 0, 0);
const cameraPointTo = new THREE.Vector3(0, 0, -1);

const unitZ = new THREE.Vector3(0, 0, 1);
const unitY = new THREE.Vector3(0, 1, 0);
const unitNegY = new THREE.Vector3(0, -1, 0);
const unitX = new THREE.Vector3(1, 0, 0);
const unitNegX = new THREE.Vector3(-1, 0, 0);
// true 表示 用平面切三角面前 就先对毛刺面进行剔除
const removeRagsBeforeCut = false;
// ──────────────┐          正常三角面
//      ↑        │← 毛刺面      ↓
//   正常三角面    ├─────────────────
//               │← 毛刺面
// 预先剔除毛刺面后，可能会造成若干条切割折线不能连接成一条折线，破坏连续性
// graphConnectDistance 定义连通图之间的最小距离小于或等于这个数值时，也认为两个图是连通的,可以合并为一个图
const graphConnectDistance = 0.05;
const center = new THREE.Vector3();
const _quat = new THREE.Quaternion();
const _quatZy = new THREE.Quaternion().setFromUnitVectors(unitZ, unitY);
const _spherical = new THREE.Spherical()
const _matRot = new THREE.Matrix4();
const _matInv = new THREE.Matrix4();

function getTriangleMats(triangle) {
  const {a, b, c} = triangle;
  center.copy(a).add(b).add(c).divideScalar(3);
  triangle.getNormal(_v3);
  _quat.setFromUnitVectors(unitZ, _v3);
  _matRot.makeRotationFromQuaternion(_quat);
  _matRot.setPosition(center);
  _matInv.copy(_matRot).invert();
  // const arr0 = [a, b, c];
  // const arr = arr0.map(it => it.clone().applyMatrix4(_matInv))
  return {mat23: _matRot, mat32: _matInv};
}

const showPlaneHelpers = false;
const planeHelpers = [];
const minimum = 0.005;
export function equalRoughly(pointA, pointB) {
  return Math.abs(pointA.x - pointB.x) <= minimum && Math.abs(pointA.y - pointB.y) <= minimum
    && Math.abs(pointA.z - pointB.z) <= minimum
}

export function arrIncludesPoint(arr, point, precise) {
  return arr.find(it => precise ? it.equals(point) : equalRoughly(it, point));
}
function arrIncludesLine(arr, line) {
  const s = line.start;
  const e = line.end;
  return arr.find(it => {
    return (equalRoughly(it.start, s) && equalRoughly(it.end, e)) ||
      (equalRoughly(it.start, e) && equalRoughly(it.end, s))
  });
}

function initPlaneLeftAndRight(lineStart, lineEnd, cameraPosition, cameraRotation) {
  const dirEyeStart = lineStart.clone().sub(cameraPosition);
  const dirEyeEnd = lineEnd.clone().sub(cameraPosition);
  const eyeUp = cameraUp.clone().applyEuler(cameraRotation);
  let normalStart = dirEyeStart.cross(eyeUp).normalize();
  let normalEnd = dirEyeEnd.cross(eyeUp).normalize();
  const dir = lineEnd.clone().sub(lineStart).normalize();
  const dot = dir.dot(normalStart);
  if (Math.abs(dot) <= 0.02) {
    // lineStart, lineEnd 形成竖直线段时，可能使得_planeStart这两个_planeEnd平面重合，两个平面的法向量都在同一直线上，
    // 所以重新设置平面朝向，避免出现这种情况，使lineStart只位于平面_planeStart上，lineEnd只位于平面_planeEnd平面上
    const eyeLeft = cameraLeft.clone().applyEuler(cameraRotation);
    normalStart = dirEyeStart.cross(eyeLeft).normalize();
    normalEnd = dirEyeEnd.cross(eyeLeft).normalize();
  }
  _planeStart.setFromNormalAndCoplanarPoint(normalStart, lineStart);
  _planeEnd.setFromNormalAndCoplanarPoint(normalEnd, lineEnd);
  if (_planeStart.distanceToPoint(lineEnd) < 0) {
    _planeStart.negate();
  }
  if (_planeEnd.distanceToPoint(lineStart) < 0) {
    _planeEnd.negate();
  }
}

export function meshToTriangles(mesh, output) {
  const posAttr = mesh.geometry.attributes.position;
  if (mesh.geometry.index) {
    const indexArray = mesh.geometry.index.array;
    for (let i = 0; i < indexArray.length; i += 3) {
      const triangle = new THREE.Triangle();
      const indices = [indexArray[i], indexArray[i + 1], indexArray[i + 2]];
      triangle.setFromAttributeAndIndices(posAttr, ...indices);
      if (removeRagsBeforeCut) {
        triangle.getNormal(_normal);
        const dotY = unitY.dot(_normal);
        const dotNegY = unitNegY.dot(_normal);
        const dotX = unitX.dot(_normal);
        const dotNegX = unitNegX.dot(_normal);
        if (dotY >= 0.999 || dotNegY >= 0.999 || dotX >= 0.999 || dotNegX >= 0.999) {
          // 基于经验的毛刺面 预先剔除
          console.log('预先剔除毛刺面: ', indices.join(','));
          continue;
        }
      }
      const {a, b, c} = triangle;
      [a, b, c].forEach(it => it.applyMatrix4(mesh.matrixWorld));
      triangle.indices = indices;
      triangle.name = indices.join(','); // for debug
      output.push(triangle);
    }
  } else {
    for (let i = 0; i < posAttr.count; i += 3) {
      const triangle = new THREE.Triangle();
      triangle.setFromAttributeAndIndices(posAttr, i, i + 1, i + 2);
      output.push(triangle);
    }
  }

  return output;
}

function trianglesToGeometry(triangles) {
  const arrVector3s = [];
  triangles.forEach(triangle => {
    const {a, b, c} = triangle;
    arrVector3s.push(a, b, c);
  });
  const geometry = new THREE.BufferGeometry();
  geometry.setAttribute('position', new THREE.BufferAttribute(flatten(arrVector3s), 3));
  return geometry;
}

function triangleToArrays(triangle, outputPosition, outputIndex) {
  const {a, b, c} = triangle;
  outputPosition.push(a, b, c);
  const offset = outputIndex.length;
  outputIndex.push(offset, offset + 1, offset + 2);
}

function triangleIntersectsPlane(triangle, plane) {
  const {a, b, c} = triangle;
  const distA = plane.distanceToPoint(a);
  const distB = plane.distanceToPoint(b);
  const distC = plane.distanceToPoint(c);
  if (distA === 0 || distB === 0 || distC === 0) {
    return true;
  }
  const intersected = distA * distB < 0 || distB * distC < 0 || distC * distA < 0;
  return intersected;
}

function triangleBetweenPlanes(triangle, planeA, planeB) {
  const {a, b, c} = triangle;
  const arr = [a, b, c];
  const underPlaneA = arr.filter(it => planeA.distanceToPoint(it) <= 0);
  const underPlaneB = arr.filter(it => planeB.distanceToPoint(it) <= 0);
  return !(underPlaneA.length === 3 || underPlaneB.length === 3);
}

function triangleAbovePlane(triangle, plane) {
  const {a, b, c} = triangle;
  const distA = plane.distanceToPoint(a);
  const distB = plane.distanceToPoint(b);
  const distC = plane.distanceToPoint(c);
  return distA >= -minimum && distB >= -minimum && distC >= -minimum;
}

function triangleAbovePlanes(triangle, planes) {
  const abovePlanes = planes.filter(plane => triangleAbovePlane(triangle, plane));
  return planes.length === abovePlanes.length;
}

function getTrianglePlaneIntersect(triangle, plane) {
  const {a, b, c} = triangle;
  _line.set(a, b);
  const p0 = plane.intersectLine(_line, _v0);
  _line.set(b, c);
  const p1 = plane.intersectLine(_line, _v1);
  _line.set(c, a);
  const p2 = plane.intersectLine(_line, _v2);
  const intersection = [];
  if (p0) {
    intersection.push(p0.clone());
  }
  if (p1 && !arrIncludesPoint(intersection, p1, true)) {
    intersection.push(p1.clone());
  }
  if (p2 && !arrIncludesPoint(intersection, p2, true)) {
    intersection.push(p2.clone());
  }
  return intersection;
}

function sliceSegmentByPlanes(planeA, planeB, q0, q1) {
  const dA0 = planeA.distanceToPoint(q0);
  const dB0 = planeB.distanceToPoint(q0);
  const dA1 = planeA.distanceToPoint(q1);
  const dB1 = planeB.distanceToPoint(q1);
  const q0InAngle = (dA0 > 0 && dB0 > 0) || (dA0 === 0 && dA1 >= 0) || (dB0 === 0 && dB1 >= 0);
  const q1InAngle = (dA1 > 0 && dB1 > 0) || (dA1 === 0 && dA0 >= 0) || (dB1 === 0 && dB0 >= 0);
  if (q0InAngle && q1InAngle) {
    return [q0, q1];
  }
  _line1.set(q0, q1);
  if (q0InAngle) {
    const inter = planeA.intersectLine(_line1, new THREE.Vector3()) || planeB.intersectLine(_line1, new THREE.Vector3());
    if (!inter) {
      console.error('sliceSegmentByPlanes error: ', dA0, dB0, dA1, dB1);
      return [q0, q1];
    }
    return [q0, inter];
  } else if (q1InAngle) {
    const inter = planeA.intersectLine(_line1, new THREE.Vector3()) || planeB.intersectLine(_line1, new THREE.Vector3());
    if (!inter) {
      console.error('sliceSegmentByPlanes error: ', dA0, dB0, dA1, dB1);
      return [q0, q1];
    }
    return [q1, inter];
  } else {
    const interA = planeA.intersectLine(_line1, new THREE.Vector3());
    const interB = planeB.intersectLine(_line1, new THREE.Vector3());
    if (interA && interB) {
      return [interA, interB];
    } else {
      return [];
    }
  }
}

export function findTriangleNeighbors(trianglesAll, excludes, triangle, precise = true) {
  const neighbors = [];
  const points0 = [triangle.a, triangle.b, triangle.c];
  trianglesAll.forEach(tri => {
    if (excludes.includes(tri)) {
      return;
    }
    const {a, b, c} = tri;
    const points = [a, b, c]
    const common = [];
    points.forEach(it => {
      if (arrIncludesPoint(points0, it, precise)) {
        common.push(it);
      }
    });
    if (common.length > 1) {
      neighbors.push(tri);
    }
  });
  return neighbors;
}

function findTrianglesInArea(triangleToCutLines, trianglesAll, cutPlanes, trianglesBorders, output = []) {
  for (let i = 0; i < trianglesBorders.length; i++) {
    const borderTriangle = trianglesBorders[i];
    const excludes = trianglesBorders.concat(output);
    const neighbors = findTriangleNeighbors(trianglesAll, excludes, borderTriangle);
    const first = neighbors.find(it => triangleAbovePlanes(it, cutPlanes));
    if (!first) {
      continue;
    }
    const bfs = [first];
    output.push(first);
    while (bfs.length > 0) {
      const triangle = bfs.shift();
      const arr = findTriangleNeighbors(trianglesAll, excludes, triangle);
      excludes.push(...arr);
      const inAreaTriangles = arr.filter(it => triangleAbovePlanes(it, cutPlanes))
      output.push(...inAreaTriangles);
      bfs.push(...inAreaTriangles);
    }
  }
  return output;
}

function triangulateBorderTriangle(cutLines, contourCutLines, borderTriangle) {
  const arr = [cutLines[0].start, cutLines[0].end];
  for (let i = 1; i < cutLines.length; i++) {
    const {start, end} = cutLines[i];
    if (!arrIncludesPoint(arr, start, true)) {
      arr.push(start);
    }
    if (!arrIncludesPoint(arr, end, true)) {
      arr.push(end);
    }
  }

  const cutPlanes = cutLines.map(it => it.plane);
  const points = [borderTriangle.a, borderTriangle.b, borderTriangle.c];
  // 保存位于所有切割平面上方的三角面片顶点
  const abovePlanePoints = points.filter(it => {
    let distances = cutPlanes.map(plane => plane.distanceToPoint(it));
    distances = distances.filter(it => it > 0);
    return distances.length === cutPlanes.length;
  });
  const normal = borderTriangle.getNormal(new THREE.Vector3());
  arr.push(...abovePlanePoints);
  if (arr.length === 3) {
    const indices = [];
    _triangle.set(...arr);
    _triangle.getNormal(_v3);
    if (_v3.dot(normal) > 0) {
      indices.push(0, 1, 2);
    } else {
      indices.push(0, 2, 1);
    }
    return {position: arr, indices};
  } else {
    const {mat23, mat32} = getTriangleMats(borderTriangle);
    const arr2d = arr.map(it => it.clone().applyMatrix4(mat32));
    const contour2d = findConvexHull(arr2d)
    if (!THREE.ShapeUtils.isClockWise(contour2d)) {
      contour2d.reverse();
    }
    const contour3d = contour2d.map(it => new THREE.Vector3(it.x, it.y, 0).applyMatrix4(mat23));

    const indices = [];
    const faces = THREE.ShapeUtils.triangulateShape(contour2d, []);
    for (let i = 0; i < faces.length; i++) {
      const face = faces[i];
      const pts = face.map(it => contour3d[it]);
      _triangle.set(...pts);
      _triangle.getNormal(_v3);
      if (_v3.dot(normal) > 0) {
        indices.push(...face);
      } else {
        indices.push(face[0], face[2], face[1]);
      }
    }
    return {position: contour3d, indices};
  }
}

// 线段联通图
class LineGraph {
  /**
   * @type {THREE.Vector3[]}
   */
  points = []
  /**
   * @type {CutLine[]}
   */
  lines = []
  keyPoints = []
  constructor(line) {
    this.addLine(line);
  }

  getLen() {
    const l = this.lines.map(it => it.len).reduce((a, b) => a + b);
    return l;
  }

  getLinesData(roughly) {
    const target = [];
    this.lines.forEach(line => {
      const start = roughly ? toFixedVector(line.start.clone(), 3) : line.start;
      const end = roughly ? toFixedVector(line.end.clone(), 3) : line.end;
      target.push(start.toArray(), end.toArray());
    });
    return JSON.stringify(target);
  }

  connectionToGraph(other) {
    const lines0 = this.lines;
    const lines1 = other.lines;
    let minDist = Infinity;
    const linkedLines = [];
    for (let i = 0; i < lines0.length; i++) {
      const line = lines0[i];
      for (let j = 0; j < lines1.length; j++) {
        const lineOther = lines1[j];
        const dist = line.distanceToLine(lineOther);
        if (minDist > dist) {
          minDist = dist;
          linkedLines[0] = line;
          linkedLines[1] = lineOther;
        }
      }
    }
    return {minDist, linkedLines};
  }

  containPoints(point) {
    return this.points.includes(point) || arrIncludesPoint(this.points, point);
  }

  addLine(line) {
    this.lines.push(line);
    const {start, end} = line;
    if (!this.containPoints(start)) {
      this.points.push(start);
    }
    if (!this.containPoints(end)) {
      this.points.push(end);
    }
  }

  hasKeyPoints(points) {
    this.keyPoints.length = 0;
    for (let i = 0; i < points.length; i++) {
      if (this.containPoints(points[i])) {
        this.keyPoints.push(points[i]);
      }
    }
    return this.keyPoints.length > 0;
  }

  findPointNeighbors(point, excludeLines) {
    const neighborPoints = [];
    const neighborLines = [];
    this.lines.forEach(line => {
      if (excludeLines.includes(line)) {
        return;
      }
      if (arrIncludesLine(excludeLines, line)) {
        return;
      }
      const otherPoint = line.endPointWith(point);
      if (otherPoint) {
        neighborPoints.push(otherPoint);
        neighborLines.push(line);
        // if (otherPoint === line.start) {
        //   line.switchStartEnd();
        // }
      }
    });
    return {neighborPoints, neighborLines};
  }

  /**
   * 寻找切割折线组成的回环
   * @param {THREE.Vector3} startPoint
   * @param {CutLine} startLine
   * @return {CutLine[]}
   * @private
   */
  _findLoop(startPoint, startLine) {
    const excludeLines = [startLine];
    const endPoint = startLine.endPointWith(startPoint);
    const bfsLines = [startLine];
    const bfs = [endPoint];
    let loop;
    while (bfs.length > 0) {
      const pt = bfs.shift();
      const curLine = bfsLines.shift();
      const obj = this.findPointNeighbors(pt, excludeLines);
      excludeLines.push(...obj.neighborLines);
      bfs.push(...obj.neighborPoints);
      obj.neighborLines.forEach(it => it.prev = curLine);
      bfsLines.push(...obj.neighborLines);
      const loopStart = arrIncludesPoint(obj.neighborPoints, startPoint);
      if (loopStart) {
        const index = obj.neighborPoints.indexOf(loopStart);
        loop = obj.neighborLines[index];
        break;
      }
    }
    if (!loop) {
      return [];
    }
    const contour = [loop];
    while (loop) {
      loop = loop.prev;
      if (loop) {
        contour.push(loop);
      }
    }
    contour.reverse();
    return contour;
  }

  /**
   * 寻找切割折线组成的轮廓
   * @return {CutLine[]}
   */
  findContour() {
    const neighbors = this.points.map(it => this.findPointNeighbors(it, []));
    const maxNum = Math.max(...neighbors.map(it => it.neighborPoints.length));
    let startNeighborIndex = neighbors.findIndex(it => it.neighborPoints.length === maxNum);

    const startPoint = this.points[startNeighborIndex];
    const neighbor = neighbors[startNeighborIndex];
    for (let i = 0; i < neighbor.neighborLines.length; i++) {
      const contour = this._findLoop(startPoint, neighbor.neighborLines[i]);
      if (contour.length > 2) {
        return contour;
      }
    }
    return [];
  }
}

class CutLine {
  start
  end
  plane
  len = 0
  /**
   * 当前折线的前一个
   * @type {null | CutLine}
   */
  prev = null
  constructor(s, e, p) {
    this.start = s;
    this.end = e;
    this.plane = p;
    this.len = s.distanceTo(e);
  }

  endPointWith(point) {
    const s = this.start;
    const e = this.end;
    if (s === point || equalRoughly(point, s)) {
      return this.end;
    } else if (e === point || equalRoughly(point, e)) {
      return this.start;
    }
    return null;
  }

  distanceToLine(other) {
    const dist0 = this.start.distanceTo(other.start);
    const dist1 = this.start.distanceTo(other.end);
    const dist2 = this.end.distanceTo(other.start);
    const dist3 = this.end.distanceTo(other.end);
    return Math.min(dist0, dist1, dist2, dist3);
  }
}

function retrieveLineGraphs(cutLines) {
  const graphs = [];
  while(cutLines.length) {
    const line0 = cutLines.shift();
    const graph = new LineGraph(line0);
    while (true) {
      const nextLine = cutLines.find(line => {
        const {start, end} = line;
        if (graph.containPoints(start) || graph.containPoints(end)) {
          return true;
        }
        return false;
      });
      if (nextLine) {
        graph.addLine(nextLine);
        removeArrayItem(cutLines, nextLine);
      } else {
        graphs.push(graph);
        break;
      }
    }
  }
  return graphs;
}

export default class ShapeExtract {
  /**
   * 三维场景实例
   * @type {World3d}
   */
  world3d
  // 缓存，能够快速通过 tile 瓦片网格找到 所有组成该网格的三角面片
  toTrianglesMap = new Map();
  /**
   * 经过cutPoints 过滤后的切割折线, 并且这些折线首尾相连组成一个轮廓
   * @type {CutLine[]}
   */
  cutLinesRefined = [];
  /**
   * 切割平面的集合，这些切割平面对特定的平面进行切割后，可以形成一个闭合图形，
   * 目前只支持这个闭合图形为凸多边形，只支持凸包切割
   * @type {THREE.Plane[]}
   */
  cutPlanes = [];
  /**
   * 射线撞击 tile瓦片网格表面产生的顶点，用于过滤切割折线
   * @type {THREE.Vector3[]}
   */
  cutPoints = [];
  /**
   * 相机的位置和姿态
   * @type {number[][]}
   */
  cameraStates = []
  /**
   * 保存所有被切割平面割过的原始三角面片
   * @type {THREE.Triangle[]}
   */
  slicedTriangles = [];
  /**
   * 保存来自多个tile瓦片网格的三角面片
   * @type {THREE.Triangle[]}
   */
  trianglesAll = [];
  /**
   * 保存三角面片 和切割折线 一对多的对应关系
   * @type {Map<THREE.Triangle, CutLine[]>}
   */
  triangleToCutLines = new Map();
  ragNormal = new THREE.Vector3();
  ragEditTriangles = [];
  markedRagTriangles = [];
  ragMesh;
  _freezeUndo = false;
  _undo = new UndoSlice()

  constructor(world3d) {
    this.world3d = world3d;
  }

  _addCutPoint(point) {
    if (!arrIncludesPoint(this.cutPoints, point)) {
      this.cutPoints.push(point);
      this._undo.addPoints.push(point);
    }
  }
  _addSlicedTriangle(triangle) {
    if (!this.slicedTriangles.includes(triangle)) {
      this.slicedTriangles.push(triangle);
      this._undo.addSlicedTriangles.push(triangle);
    }
  }
  clearUndo() {
    this._undo.clearStack();
  }
  clearCutCache() {
    this.cutLinesRefined.length = 0;
    this.cutPlanes.length = 0;
    this.cutPoints.length = 0;
    this.cameraStates.length = 0;
    this.slicedTriangles.length = 0;
    this.triangleToCutLines.clear();
    this.trianglesAll.length = 0;
  }

  // 目前只支持凸包切割，把所有切割平面的极性都确定下来
  _setCutPlanesPolarities() {
    planeHelpers.forEach(it => it.removeFromParent());
    planeHelpers.length = 0;
    const [a, b, c] = this.cutPoints;
    const pointInside = a.clone().add(b).add(c).divideScalar(3);
    this.cutPlanes.forEach((plane, index) => {
      if (plane.distanceToPoint(pointInside) < 0) {
        plane.negate();
      }
      if (showPlaneHelpers) {
        const planePos = this.cutPoints[index].clone();
        if (index === this.cutPlanes.length - 1) {
          planePos.add(this.cutPoints[0]).divideScalar(2);
        } else {
          planePos.add(this.cutPoints[index + 1]).divideScalar(2);
        }
        const planeHelper = new PlaneHelper2(plane, 2, 0x00ff00, planePos);
        this.world3d.scene.add(planeHelper);
        planeHelpers.push(planeHelper);
      }
    });
  }

  computeConvexAreaGeometry() {
    this._setCutPlanesPolarities();
    const borderTriangles = this.slicedTriangles;
    const arrIndex = [];
    const arrVector3s = [];
    const trianglesInArea = [];
    findTrianglesInArea(this.triangleToCutLines, this.trianglesAll, this.cutPlanes, borderTriangles, trianglesInArea);
    trianglesInArea.forEach(triangle => triangleToArrays(triangle, arrVector3s, arrIndex));
    const geometryInArea = new THREE.BufferGeometry();
    if (trianglesInArea.length) {
      geometryInArea.setAttribute('position', new THREE.BufferAttribute(flatten(arrVector3s), 3));
      geometryInArea.setIndex(arrIndex);
    }

    const verticesIndicesObjs = [];
    const geometriesFromBorder = [];
    borderTriangles.forEach(bTriangle => {
      if (trianglesInArea.includes(bTriangle)) {
        return;
      }
      const cutLines = this.triangleToCutLines.get(bTriangle);
      const obj = triangulateBorderTriangle(cutLines, this.cutLinesRefined, bTriangle);
      verticesIndicesObjs.push(obj);
      const geometry = new THREE.BufferGeometry();
      geometry.setAttribute('position', new THREE.BufferAttribute(flatten(obj.position), 3));
      geometry.setIndex(obj.indices);
      geometriesFromBorder.push(geometry);
    });
    if (trianglesInArea.length) {
      geometriesFromBorder.push(geometryInArea);
    }
    const geometry = mergeBufferGeometries(geometriesFromBorder, false);
    return geometry;
  }

  computeClosedAreaGeometry4Debug() {
    const arr = this.world3d.store.surfacesAreaMeshes;
    if (!arr.length) {
      return;
    }
    let selectSurface = this.world3d.store.pickingSurfaceMesh();
    if (!selectSurface) {
      selectSurface = arr[arr.length - 1];
    }
    const vo = selectSurface.vo;
    const params = createParams(vo.cutPoints, vo.cameraStates);
    const position = params[0][2];
    const rotation = params[0][3];
    const {camera, cameraControls} = this.world3d;
    camera.position.copy(position);
    const target = new THREE.Vector3(0, 0, -2).applyEuler(rotation).add(position);
    cameraControls.target.copy(target);
    cameraControls.update();
    this.clearCutCache();
    this._freezeUndo = true;
    params.forEach(arr => {
      this.computeIntersectSegments(...arr);
    });
    this.computeConvexAreaGeometry();
  }

  computeClosedAreaGeometry() {
    const paramsLst = CutPointsDivider.divide(this.cutPoints, this.cameraStates);
    let geometryMerged;
    if (!paramsLst.length) {
      geometryMerged = this.computeConvexAreaGeometry();
    } else {
      this._freezeUndo = true;
      // 注意：这里要对这两个属性进行备份，因为之后的 convexMesh.createVO()方法会使用这两个属性
      const pointsBak = this.cutPoints.slice();
      const statesBak = this.cameraStates.slice();
      console.log(`拆分为: ${paramsLst.length} 个凸形切割`);
      const geometries = [];
      for (let i = 0; i < paramsLst.length; i++) {
        this.clearCutCache();
        const params = paramsLst[i];
        params.forEach(arr => {
          this.computeIntersectSegments(...arr);
        });
        geometries.push(this.computeConvexAreaGeometry());
      }
      this._freezeUndo = false;
      this.cutPoints = pointsBak;
      this.cameraStates = statesBak;
      geometryMerged = mergeBufferGeometries(geometries, false);
    }
    const vCount0 = geometryMerged.attributes.position.count;
    const geometryArea = mergeVertices(geometryMerged);
    const vCount1 = geometryArea.attributes.position.count;
    console.log(`computeClosedAreaGeometry, vertices count: ${vCount0}, after merge: ${vCount1}`);
    // this.world3d.toggleTileLock(true);
    return geometryArea;
  }

  computeCutLines(lineStart, lineEnd) {
    // this.world3d.toggleTileLock(true);
    const {position, rotation} = this.world3d.camera;
    return this.computeIntersectSegments(lineStart, lineEnd, position, rotation);
  }

  /**
   * 计算出 tiles 网格与切割三角形相交的所有线段
   * @param {THREE.Vector3} lineStart
   * @param {THREE.Vector3} lineEnd
   * @param {THREE.Vector3} cameraPosition
   * @param {THREE.Euler} cameraRotation
   * @param {boolean} fromUndo
   * @return {THREE.Vector3[]} 多条线段的端点
   */
  computeIntersectSegments(lineStart, lineEnd, cameraPosition, cameraRotation, fromUndo = false) {
    console.log('max single distance: ', lineStart.distanceTo(lineEnd));
    const tiles = this.world3d.tiles;
    if (!tiles.group) {
      return [];
    }
    if (!fromUndo) {
      this._addCutPoint(lineStart);
      this._addCutPoint(lineEnd);
    }
    const cutTriangle = new THREE.Triangle();
    const cutPlane = new THREE.Plane();
    cutTriangle.set(lineStart, lineEnd, cameraPosition);
    cutTriangle.getPlane(cutPlane);
    if (!fromUndo) {
      this.cutPlanes.push(cutPlane);
      this._undo.addPlane = cutPlane;
    }
    initPlaneLeftAndRight(lineStart, lineEnd, cameraPosition, cameraRotation);
    const intersectedMeshes = [];
    const trianglesAll = [];
    tiles.group.traverse((child) => {
      if (child.isMesh && child.visible) {
        _box.copy(child.geometry.boundingBox).applyMatrix4(child.matrixWorld);
        const intersect = cutTriangle.intersectsBox(_box);
        if (intersect) {
          intersectedMeshes.push(child);
          const cachedTriangles = this.toTrianglesMap.get(child);
          if (cachedTriangles) {
            trianglesAll.push(...cachedTriangles);
          } else {
            const trianglesInChild = []
            meshToTriangles(child, trianglesInChild);
            this.toTrianglesMap.set(child, trianglesInChild);
            trianglesAll.push(...trianglesInChild);
          }
        }
      }
    });
    const cutLines = [];
    const mapCutLineToTriangle = new Map();
    const segments = [];
    for (let i = 0; i < trianglesAll.length; i++) {
      const triangle = trianglesAll[i];
      if (!fromUndo && !this.trianglesAll.includes(triangle)) {
        this.trianglesAll.push(triangle);
        if (!this._freezeUndo)
          this._undo.addTriangles.push(triangle);
      }
      if (!triangleIntersectsPlane(triangle, cutPlane)) {
        continue;
      }
      if (!triangleBetweenPlanes(triangle, _planeStart, _planeEnd)) {
        continue;
      }
      const points = getTrianglePlaneIntersect(triangle, cutPlane);
      if (points.length < 2) {
        continue;
      }
      const seg = sliceSegmentByPlanes(_planeStart, _planeEnd, points[0], points[1]);
      if (seg.length < 2) {
        continue;
      }
      // segments.push(...seg)
      const cutLine = new CutLine(seg[0], seg[1], cutPlane);
      cutLines.push(cutLine);
      mapCutLineToTriangle.set(cutLine, triangle);
    }
    const graphs = retrieveLineGraphs(cutLines);
    const graphsFiltered = graphs.filter(it => it.hasKeyPoints([lineStart, lineEnd]));
    if (graphConnectDistance > 0) {
      const graphArr = arrAsubB(graphs, graphsFiltered);
      const graphAdded = graphArr.filter(it => graphsFiltered.find(graph => graph.connectionToGraph(it).minDist <= graphConnectDistance));
      graphsFiltered.push(...graphAdded);
    }
    graphsFiltered.forEach(graph => {
      if (!fromUndo) {
        this.cutLinesRefined = this.cutLinesRefined.concat(graph.lines);
        if (!this._freezeUndo)
          this._undo.addCutLines.push(...graph.lines);
      }
      graph.lines.forEach(line => {
        segments.push(line.start, line.end);
        if (!fromUndo) {
          const tri = mapCutLineToTriangle.get(line);
          if (!this._freezeUndo)
            this._undo.addTriangleToCutLines(tri, line);
          this._addSlicedTriangle(tri);
          const cutLineArr = this.triangleToCutLines.get(tri);
          if (cutLineArr) {
            cutLineArr.push(line);
          } else {
            this.triangleToCutLines.set(tri, [line]);
          }
        }
      });
    });
    if (!fromUndo) {
      const arr1 = cameraPosition.toArray();
      const arr2 = [cameraRotation.x, cameraRotation.y, cameraRotation.z];
      this._undo.addCameraState = arr1.concat(arr2);
      this.cameraStates.push(this._undo.addCameraState);
      if (!this._freezeUndo)
        this._undo.addUndoStack();
    }
    return segments;
  }

  sliceUndo() {
    this._undo.undo(this)
  }
  sliceRedo() {
    this._undo.redo(this)
  }

  clearRagMesh() {
    const markingRag = this.ragEditTriangles.length;
    if (!markingRag) {
      return;
    }
    this.markedRagTriangles.length = 0;
    if (this.ragMesh) {
      this.ragMesh.removeFromParent();
    }
  }

  pointerUpUnmoved(event) {
    const arr = this.world3d.store.surfacesAreaMeshes;
    if (!arr.length) {
      return;
    }
    const surfaceMesh = this.world3d.store.pickingSurfaceMesh();
    if (!surfaceMesh) {
      return;
    }
    const results = this.world3d.mouseRaycaster.intersectObject(
      surfaceMesh,
      false,
    );
    if (!results.length) {
      return;
    }
    // updateDebugTriangle(this.world3d.scene, results[0]);
    this.ragNormal.copy(results[0].face.normal);
    this.updateRagMesh();
  }

  _showRagMesh(color = '#d00') {
    if (!this.markedRagTriangles.length) {
      return;
    }
    if (this.ragMesh) {
      this.ragMesh.removeFromParent();
    }
    const geometry = trianglesToGeometry(this.markedRagTriangles);
    const mtl = new THREE.MeshBasicMaterial({color: color, transparent: true, opacity: 0.9});
    const mesh = new THREE.Mesh(geometry, mtl);
    this.world3d.scene.add(mesh);
    this.ragMesh = mesh;
  }

  updateRagMesh() {
    const ragTris = this.ragEditTriangles.filter(triangle => {
      triangle.getNormal(_normal);
      const dot = _normal.dot(this.ragNormal);
      return dot > 0.999 || dot < -0.999;
    });
    const len0 = this.markedRagTriangles.length;
    ragTris.forEach(tri => {
      if (!this.markedRagTriangles.includes(tri)) {
        this.markedRagTriangles.push(tri);
      }
    });
    if (len0 === this.markedRagTriangles.length) {
      return;
    }
    this._showRagMesh();
  }

  isMarkingRag() {
    return this.ragEditTriangles.length;
  }

  // 在标定区域网格上标定 哪些三角面是毛刺网格，毛刺网格会干扰 AI 进行航线规划
  markRagFaces() {
    const surfaceMesh = this.world3d.store.pickingSurfaceMesh();
    if (!surfaceMesh) {
      return;
    }
    if (!this.ragEditTriangles.length) {
      meshToTriangles(surfaceMesh, this.ragEditTriangles);
    }
    if (!this.ragEditTriangles.length) {
      return;
    }
    surfaceMesh.material.wireframe = true;
    // this.world3d.toggleWireframe(true);
    this.world3d.toggleTileVisible(false);
    // 猜测哪些三角面是 毛刺面，只能保证大概率正确
    this.ragEditTriangles.forEach(triangle => {
      triangle.getNormal(_normal);
      const dotY = unitY.dot(_normal);
      const dotNegY = unitNegY.dot(_normal);
      // const dotX = unitX.dot(_normal);
      // const dotNegX = unitNegX.dot(_normal);
      // || dotX >= 0.999 || dotNegX >= 0.999
      if (dotY >= 0.999 || dotNegY >= 0.999 ) {
        this.markedRagTriangles.push(triangle);
      }
    });
    this._showRagMesh();
  }
  // 对标定好的若干个毛刺三角面片进行删除
  removeRagFaces() {
    const surfaceMesh = this.world3d.store.pickingSurfaceMesh();
    if (!surfaceMesh) {
      return;
    }
    if (this.ragEditTriangles.length && this.markedRagTriangles.length) {
      arrAsubB(this.ragEditTriangles, this.markedRagTriangles);
      const geometry0 = trianglesToGeometry(this.ragEditTriangles);
      const geometry = mergeVertices(geometry0);
      const newSurfaceMesh = new ConvexAreaMesh(geometry, surfaceMesh.material);
      newSurfaceMesh.vo = surfaceMesh.vo;
      newSurfaceMesh.initContour(surfaceMesh.children);
      this.world3d.scene.add(newSurfaceMesh);
      surfaceMesh.removeFromParent();
      const arr = this.world3d.store.surfacesAreaMeshes;
      arr[arr.indexOf(surfaceMesh)] = newSurfaceMesh;
    }

    this.ragEditTriangles.length = 0;
    this.markedRagTriangles.length = 0;
    if (this.ragMesh) {
      this.ragMesh.removeFromParent();
      this.ragMesh = null;
    }
    surfaceMesh.material.wireframe = false;
    this.world3d.toggleTileVisible(true);
  }
  testRoute() {
    const surfaceMesh = this.world3d.store.pickingSurfaceMesh();
    if (!surfaceMesh) {
      return;
    }
    const triangles = meshToTriangles(surfaceMesh, []);
    // const areas = SurfaceRoutePlan.assignTrianglesToAreas(triangles);
    // console.log(areas.length)
    const hArr = triangles.filter(tri => {
      tri.getNormal(_normal).applyQuaternion(_quatZy);
      _spherical.setFromVector3(_normal);
      return ConfigRoute.isHorizontal(_spherical.phi);
    });
    this.markedRagTriangles = hArr;
    surfaceMesh.material.wireframe = true;
    this._showRagMesh('#006')
  }
}
